package com.wrial.kind.search;
/*
 * @Author  Wrial
 * @Date Created in 17:43 2020/8/25
 * @Description 统计一个数字在排序数组中出现的次数。
 * 输入: nums = [5,7,7,8,8,10], target = 8
   输出: 2
 */

public class SearchOrderNumCount {
    /**
     * 因为是在有序数组中查找数字，可以使用二分,但是由于target不唯一，因此需要得到最左边target下标和最右边target下标
     * 1.两次二分查找，分别找出左边界和右边界
     * 2.找出当前target的右边和target-1的右边下标然后相减
     */

    public int search(int[] nums, int target) {
        if (nums.length == 0) return 0;
        int i = 0, left;
        int j = nums.length - 1, right = nums.length - 1;
        // 找left
        while (i <= j) {
            int mid = (i + j) / 2;
            if (target <= nums[mid]) {
                j = mid - 1;
            } else i = mid + 1;
        }
        left = j;
        //找right
        i = 0;
        j = right;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (target >= nums[mid]) {
                i = mid + 1;
            } else j = mid - 1;
        }
        right = i;
        return right - left - 1;
    }
}
